#在遗传算法中，一个个体一般只包含一条染色体。染色体上包含这一组基因。
#基因 ( Gene ) ：一个遗传因子。
#染色体 ( Chromosome ) ：一组的基因。
#个体 ( individual )：单个生物。
#群体：一群个体

#自变量只有x时，只有一个gene，此时：
        #一个个体=一条染色体=一个基因

#将x表达为gene的过程，称之为编码，常见的编码格式有二进制编码和浮点编码。本文采用2进制编码：

#设我们求解精度为 n=0.01
 
#f(x)=x∗sin(10∗π∗x)+2
#x∈[5,8]

#那么我们需要将x的区间[5，8]，切分成(2+1)/0.01=300 份。
#又因为采用二进制编码所以实际需要的编码位数为：2^8=256<300<2^9=512
#故当我们需要精度为0.01时，采用二进制编码最少需要9位数。
#那么实际的求解精度为： n=3/512≈0.00586
#有编码就存在着解码，按照本文的例子，可以想到以下的映射： 
#000000000 = 5
#111111111 = 8
#因此可以得到以下的解码公式：
#(000000000)into10 = 0+5 = 5
#(111111111)into10 = 512*3/512+5 = 8


import matplotlib.pyplot as plt
import random
import math

def yichuan(pop , f , jingdu):
    #1.生成初始种群
    listA = []   #亲本列表（基因型）
    for i in range(0,pop):    #生成200个个体的种群
        A = ''
        for j in range(0,14):      #每个染色体有14个基因，编码（根据精度确定基因数）
            A += str(random.randint(0,1))
        listA += [A]
    #print(listA)

    det = 10   #适应度差值(先随便赋一个比较大的值)
    t = 0   #进化次数
    list_t = []
    list_max = []
    list_det = []
    #2.开始进化
    while float(det) > jingdu:   #以精度进行循环
    #while t < 100:   #以进化次数进行循环
        t += 1   #第t次进化

        #杂交过程：随机挑选几对亲本交配
        suiji = random.randint(1,pop/2)*2
        linshi_list = []
        for i in range(0,suiji):
            linshi_list.append(random.choice(listA))
        listB = []
        #print(len(linshi_list))
        for k in range(0,int(len(linshi_list)/2)):
            a = random.randint(1,12)
            c = linshi_list[2*k][0:a] + linshi_list[2*k+1][a:]
            d = linshi_list[2*k+1][0:a] + linshi_list[2*k][a:]
            listB.append(c)
            listB.append(d)
    
        #print(listB)
        #3.变异操作（只有子代listB能发生变异,且控制越靠左的基因变异率越低）
        pc = 0.1  #变异率
        listb = []  #变异后的个体（基因型）
        for i in range(0,len(listB)):
            geti = listB[i]   #第i个个体的基因型
            for j in range(0,9):
                jiyin = geti[j]
                if random.random() < pc:
                    if jiyin == '0':
                        geti = geti[0:j]+'1'+geti[j+1:]
                    else:
                        geti = geti[0:j]+'0'+geti[j+1:]
            listb.append(geti)
        #print(listb)
        listall = listA +listb  #所有个体基因型
        #print(listall)
    
    #-----------------------------------种群杂交完毕--------------------

        #解码
        bestA = []   #亲代表现型
        bestB = []   #子代表现型
        for i in range(0,len(listA)):
            numA = int(listA[i-1],2)*100/16384
            bestA.append(numA)
        for j in range(0,len(listb)):
            numB = int(listb[j-1],2)*100/16384
            bestB.append(numB)
        #print(bestA,bestB)
        bestall = bestA +bestB   #所有个体表现型
    
        #4.计算适应度
        save_bestA = []  #储存亲本适应度
        save_bestB = []  #储存子代适应度
        for i in range(0,len(bestA)):    #计算亲本种群每个个体的适应度
            x = bestA[i]
            fA = f(x)
            save_bestA.append(fA)
        for j in range(0,len(bestB)):    #计算子代种群每个个体的适应度
            x = bestB[j]
            fB = f(x)
            save_bestB.append(fB)

        save_list = save_bestA + save_bestB   #所有个体适应度
        save = save_bestA + save_bestB
        #print('进化次数',t-1,save_bestA)

        #将表现型与适应度一一对应
        #for jiyin,biaoxian,shiying in zip(listall,bestall,save_list):
            #print(jiyin,'对应',biaoxian,'对应',shiying)


        #将save_list列表从大到小排序(冒泡)，找出前pop个最大适应度
        for i in range(len(save)):
            for j in range(i+1):
                if save[i] > save[j]:
                    # 实现2个变量的互换
                    save[i],save[j] = save[j],save[i]
        #print (save_list)
        bestAB = save[0:pop]   #前pop最佳适应度
    
        #计算适应度波动情况（方差）
        avesum = 0
        for ave in bestAB:
            avesum += ave
        average = avesum / len(bestAB)   #适应度平均值
        fangcha = 0
        for aver in bestAB:
            fangcha += math.fabs(aver-average)
        det = fangcha / len(bestAB)
        #print(bestAB)
        index_list = []
        for i in range(0,pop):
            index = save_list.index(bestAB[i])  #定位好前pop大适应度
            index_list.append(index)
        x = []
        listA = []
        for j in range(0,len(index_list)):
            listA.append(listall[index_list[j]])  #产生新的亲本
            x.append(bestall[index_list[j]])
        #print(listA)
        list_t.append(t)
        list_max.append(max(bestAB))
        list_det.append(det)
    
        X0 = [i / float(10) for i in range(0,1001)]
        Y0 = [f(x) for x in X0]
        plt.figure(t)
        plt.plot(X0,Y0,label='x(x-10)(x-15)(x-30)(x-50)(x-70)(x-85)(x-86)')
        title = '第'+str(t)+'次进化分布'
        plt.title(title,fontproperties='SimHei')  #后面用于输出中文
        plt.scatter(x,bestAB,c='r',s=5)
        plt.legend()
        #plt.savefig('进化图\\'+str(t)+'.jpg')
        plt.draw()
        plt.close(t)
    plt.plot(list_t,list_max)
    plt.title('每次进化最大值情况',fontproperties='SimHei')
    plt.show()
    plt.plot(list_t,list_det)
    plt.title('种群分布波动情况',fontproperties='SimHei')
    plt.show()

    print('x(x-10)(x-15)(x-30)(x-50)(x-70)(x-85)(x-86)')
    print(max(bestAB))
    print('进化次数=',t)
    print('最高处',x[save_list.index(max(bestAB))],max(bestAB))

    return


def f(x):
    _f = x*(x-10)*(x-15)*(x-30)*(x-50)*(x-70)*(x-85)*(x-100)/100000000000
    return _f


pop = 200   #种群个体数
jingdu = 0.000001  #精度
yichuan(pop,f,jingdu)
